package org.example.leetcode;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * file:HuadongChaungkou.class
 * function:  滑动窗口（定长、不定长、多指针）
 *
 * @author shaodan wang
 * @date 2024-07-15
 */

public class HuadongChaungkou {


    public int maxVowels(String s, int k) {
        int max = 0;
        int res = 0;
        for (int i = 0; i < k; i++) {
            char c = s.charAt(i);
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                max++;
            }
        }
        for (int i = k; i <= s.length() - k; i++) {
            max = vowelsNum(s.substring(i - 1, k + i), max);
            res = Math.max(res, max);
        }
        return res;
    }


    public int vowelsNum(String s, int max) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char start = s.charAt(0);
        if (start == 'a' || start == 'e' || start == 'i' || start == 'o' || start == 'u') {
            max--;
        }
        char end = s.charAt(s.length() - 1);
        if (end == 'a' || end == 'e' || end == 'i' || end == 'o' || end == 'u') {
            max++;
        }

        return max;
    }

    @Test
    public void test001() {
        System.out.println(maxVowels("weallloveyou", 7));
    }


    //TODO  套用规则
    //固定的滑动窗口
    public int maxVowels1(String S, int k) {
        char[] s = S.toCharArray();
        int ans = 0;
        int vowel = 0;
        for (int i = 0; i < s.length; i++) {
            // 1. 进入窗口
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                vowel++;
            }
            if (i < k - 1) { // 窗口大小不足 k
                continue;
            }
            // 2. 更新答案
            ans = Math.max(ans, vowel);
            // 3. 离开窗口
            char out = s[i - k + 1];
            if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
                vowel--;
            }
        }
        return ans;
    }

    /**
     * 滑动窗口  学生分数的最小差值
     * 给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
     * 从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
     * 返回可能的 最小差值 。
     *
     * @param nums
     * @param k
     * @return
     */


    //这个为什么会出错
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        for (int i = k - 1; i < nums.length; i++) {
            min = Math.min(min, nums[i] - nums[i - k]);
        }
        return min;
    }

    public int minimumDifference2(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = nums[k - 1] - nums[0];
        for (int i = k; i < n; i++) {
            ans = Math.min(ans, nums[i] - nums[i - k + 1]);
        }
        return ans;
    }

    @Test
    public void test003() {
//        System.out.println(minimumDifference(new int[]{90}, 1));
    }


    public int divisorSubstrings(int num, int k) {
        String strNum = String.valueOf(num);
        int max = 0;
        for (int i = 0; i <= strNum.length() - k; i++) {
            String num1 = strNum.substring(i, i + k);
            if (Integer.parseInt(num1) != 0 && num % Integer.parseInt(num1) == 0) {
                max++;
            }
        }
        return max;
    }

    @Test
    public void test002() {
        System.out.println(divisorSubstrings(30003, 3));
    }

    /**
     * 给你一个整数数组 arr 和两个整数 k 和 threshold 。
     * 请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
     *
     * @param arr
     * @param k
     * @param threshold
     * @return
     */
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int targetTh = threshold * k;
        int sum = 0;
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            sum = sum + arr[i];
            if ((i + 1) < k) { //窗口不够长
                continue;
            }
            if (sum * k >= targetTh) {
                count++;
            }
            //怎么推算出是 i - k + 1,
            sum = sum - arr[i + 1 - k];
        }
        return count;
    }

    @Test
    public void Test004() {
        System.out.println(numOfSubarrays(new int[]{2, 2, 2, 2, 5, 5, 5, 8}, 3, 4));
    }

    /**
     * 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
     * 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
     * 任何误差小于 10-5 的答案都将被视为正确答案。
     *
     * @param nums
     * @param k
     * @return
     */
    public double findMaxAverage(int[] nums, int k) {
        int max = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((i + 1) <= k) { //窗口未满
                sum = sum + nums[i];
                max = sum;
                continue;
            }
            sum = sum - nums[i - k] + nums[i];
            max = Math.max(max, sum);
        }

        return ((double) max) / k;
    }

    @Test
    public void test005() {
        System.out.println(findMaxAverage(new int[]{4, 2, 1, 3, 3}, 2));
    }


    public double findMaxAverage1(int[] nums, int k) {

        // 滑动窗口
        // 题目给出长度为k，保持双指针之间的长度固定

        int sum = 0;
        int n = nums.length;
        // 计算第一个窗口，以后的窗口只在这个窗口上减去一个旧的，添加一个新的
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        // 用第一个窗口的和初始化max
        int maxSum = sum;
        // 以后的窗口从k开始
        for (int i = k; i < n; i++) {
            // 用第一个（上一个）窗口的和减去最后一个值，然后新增一个值，就是下一个窗口
            sum = sum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, sum);
        }
        return 1.0 * maxSum / k;
    }


    /**
     * 给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。
     * 半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。
     * 如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。
     * 构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
     * x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。
     * 例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2。
     * <p>
     * <p>
     * 先将为-1的初始化好，然后中间的数据的右边为窗口的末端
     *
     * @param nums
     * @param k
     * @return
     */

    public int[] getAverages(int[] nums, int k) {
        int sum;
        int[] avg = new int[nums.length];
        if (2 * k >= nums.length) {
            Arrays.fill(avg, -1);
            return avg;
        }
        if (k == 0) {
            return nums;
        }
        sum = nums[k];
        for (int i = 0; i < k; i++) {//左边右边初始化
            avg[i] = -1;
            sum = sum + nums[i] + nums[k + i + 1];//将窗口填充到0 - 2*k
            avg[avg.length - 1 - i] = -1;
        }

        for (int j = 2 * k; j < nums.length; j++) {
            avg[j - k] = sum / (2 * k + 1);
            sum = sum - nums[j - k] + nums[j];
        }
        return avg;
    }


    //TODO 二刷建议
    public int[] getAverages1(int[] nums, int k) {
        //固定滑动窗口的解决方法，二刷
        int n = nums.length;
        long x = 2L * k + 1;
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        int j = 0;
        long sum = 0;
        for (int i = 0; i < n; i++) { // j是左边的 指针 i是右边的指针
            sum += nums[i];
            if (i - j + 1 == x) res[i - k] = (int) (sum / x);
            if (i - j + 1 >= x) sum -= nums[j++]; //向左滑动
        }
        return res;
    }

    @Test
    public void test004() {
        for (int average : getAverages(new int[]{7, 4, 3, 9, 1, 8, 5, 2, 6}, 3)) {
            System.out.println(average);

        }
    }

    /**
     * 给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。
     * 给你一个整数 k ，表示想要 连续 黑色块的数目。
     * 每一次操作中，你可以选择一个白色块将它 涂成 黑色块。
     * 请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。
     *
     * @param blocks
     * @param k
     * @return
     */
    public int minimumRecolors(String blocks, int k) {
        int res = Integer.MAX_VALUE;//最少涂黑的次数
        int count = 0;
        for (int i = 0; i < blocks.length(); i++) {
            if (blocks.charAt(i) == 'W') {
                count++;
            }
            if (i + 1 < k) { //窗口还没到k
                continue;
            }
            res = Math.min(res, count);
            if (blocks.charAt(i - k + 1) == 'W') { //减去左边
                count--;
            }
        }
        return res;
    }

    // WB BW BW
    @Test
    public void test006() {
        System.out.println(minimumRecolors("WBWBBBW", 2));
    }

    /**
     * 爱生气的书店老板
     *
     * @param customers
     * @param grumpy
     * @param minutes
     * @return
     */
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int res = 0;
        int count = 0;
        for (int i = 0; i < customers.length; i++) {//把所有不生气的时间加上去
            if (grumpy[i] == 0) {
                count = count + customers[i];
            }
        }
        for (int i = 0; i < customers.length; i++) {//固定滑动窗口，将抑制不生气的时候为1的顾客数量继续加上去
            if (grumpy[i] == 1) {
                count = count + customers[i];
            }
            if (i + 1 < minutes) {
                continue;
            }
            res = Math.max(count, res);
            if (grumpy[i - minutes + 1] == 1) {
                count = count - customers[i - minutes + 1];
            }
        }
        return res;
    }

    @Test
    public void test007() {
        System.out.println(maxSatisfied(new int[]{4, 10, 10}, new int[]{1, 1, 0}, 2));

    }

    /**
     * 几乎唯一子数组的最大和
     * 给你一个整数数组 nums 和两个正整数 m 和 k 。
     * 请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
     * 如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
     * 子数组指的是一个数组中一段连续 非空 的元素序列。
     *
     * @param nums
     * @param m
     * @param k
     * @return
     */

    public long maxSum(List<Integer> nums, int m, int k) {
        Map<Long, Long> uniqueMap = new HashMap<>(m); // key 为num val 为有多少个
        long sum = 0;
        long result = 0;
        for (int i = 0; i < nums.size(); i++) {
            uniqueMap.put(Long.valueOf(nums.get(i)), uniqueMap.getOrDefault(Long.valueOf(nums.get(i)), 0L) + 1);
            sum = sum + nums.get(i);
            if (i + 1 >= k) {
                //已经到达指定长度了
                if (uniqueMap.size() >= m) { //符合不相同元素数量
                    result = Math.max(result, sum);
                }
                //左边缩小范围
                long left = nums.get(i - k + 1);
                sum = sum - left;
                if (uniqueMap.containsKey(left)) {
                    uniqueMap.put(left, uniqueMap.get(left) - 1);
                    if (uniqueMap.get(left) <= 0) {
                        uniqueMap.remove(left);
                    }
                }
            }
        }
        return result;
    }

    @Test
    public void test008() {
        System.out.println(maxSum(Arrays.asList(996021492, 996021492, 973489433, 66259330, 554129007, 713784351, 646092981, 328987029, 469368828, 685679486, 66259330, 165954500, 731567840, 595800464, 552439059, 14673238, 157622945, 521321042, 386913607, 733723177, 330475939, 462727944, 69696035, 958945846, 648914457, 627088742, 363551051, 50748590, 400980660, 674779765, 439950964, 613843311, 385212079, 725525766, 813504429, 385212079, 66563232, 578031878, 935017574, 554725813, 456892672, 245308625, 626768145, 270964388, 554725813, 768296675, 676923124, 939689721, 115905765, 625193590, 717796816, 27972217, 277242430, 768296675, 480860474, 659230631, 570682291, 601689140, 955632265, 767424000, 251696645, 675750691, 767424000, 251696645, 767424000, 675750691, 675750691, 251696645), 8, 8));
    }

    /**
     * 题目：长度为 K 子数组中的最大和
     * 给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
     * 子数组的长度是 k，且
     * 子数组中的所有元素 各不相同 。
     * 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0。
     * 子数组 是数组中一段连续非空的元素序列。
     * 通过这个例子可以看出，start 不能直接更新 3, 2, 3, 1
     * @param nums
     * @param k
     * @return
     */
    public long maximumSubarraySum(int[] nums, int k) {
        Set<Integer> uniqueSet = new HashSet<>();
        long sum = 0;
        long max = 0;
        long start = 0;
        for (int i = 0; i < nums.length; i++) {
            if (uniqueSet.contains(nums[i])) { //说明有重复的
                start = i;
                sum = nums[i];
                uniqueSet.clear();
                uniqueSet.add(nums[i]);
            } else {//说明没有重复的
                sum = sum + nums[i];
                uniqueSet.add(nums[i]);
                if (i - start + 1 == k) { //窗口满了
                    max = Math.max(sum, max);
                    sum = sum - nums[(int) start];
                    uniqueSet.remove(nums[(int) start]);
                    start++;
                }
            }
        }
        return max;
    }

    public long maximumSubarraySum1(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length, i = 0, j = 0;
        long ans = 0, sum = 0;
        while (j < n) {
            if (set.contains(nums[j])) {
                set.remove(nums[i]);
                sum -= nums[i++];
            }
            set.add(nums[j]);
            sum += nums[j];
            if (j - i + 1 == k) {
                ans = Math.max(sum, ans);
                sum -= nums[i];
                set.remove(nums[i++]);
            }
            j++;
        }
        return ans;
    }

    @Test
    public void test009() {
        System.out.println(maximumSubarraySum(new int[]{3, 2, 3, 1}, 3));
    }


    /**
     *  无重复字符的最长子串
     *  最长不重复子串
     *  给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int max = 0;
        int right = -1;//注意这里right为什么为-1；
        //i 指向最左边的字串， right指向最右边的不重复字串
        for (int i = 0; i < s.length(); i++) {
            if(i != 0){
                set.remove(s.charAt(i-1));//每次移除前一个
            }
            //right指向最右边的不重复字串,+1相当于试探后面的字串，存在则直接跳出循环
            while (right + 1  < s.length() && !set.contains(s.charAt(right + 1))){
                set.add(s.charAt(right + 1));
                right++;
            }
            //比较这次的字串和之前最大的字串的长度谁的大
            max = Math.max(max,right - i+ 1);
        }
        return max;
    }
}
